﻿using ModelLayer;
using System;
using System.Collections.Generic;
using System.Linq;

namespace ControllerLayer.Dijkstras
{
    public class Graph
    {
        //A list for keeping the visited nodes
        private readonly List<Node> _visitedNodes;

        //A list for keeping the nodes which are reachable
        private readonly ReachableNodeList _reachableNodes;

        private readonly List<Node> _nodes;
        private readonly List<Edge> _edges;

        public Graph(List<Node> nodesList, IEnumerable<Edge> edgesList)
        {
            _visitedNodes = new List<Node>();
            _reachableNodes = new ReachableNodeList();

            _nodes = nodesList;
            _edges = new List<Edge>();
            foreach (Edge edge in edgesList)
            {
                AddEdge(edge.FirstNode.Station, edge.SecondNode.Station, edge.Distance, edge.Time);
            }
        }

        //Add a node to the graph
        public void AddNode(Station s)
        {
            var node = new Node(s);
            _nodes.Add(node);
        }

        //Add two nodes to a new connection (implemented with stations as nodes)
        public void AddEdge(Station fromStation, Station toStation, double distance, TimeSpan time)
        {
            var fromNode = _nodes.Single(n => n.Station.Id.Equals(fromStation.Id));
            var toNode = _nodes.Single(n => n.Station.Id.Equals(toStation.Id));
            var edge = new Edge(fromNode, toNode, distance, time);
            _edges.Add(edge);

            fromNode.Edges.Add(edge);
            toNode.Edges.Add(edge);
        }

        /// <summary>
        /// Returns the shortest path between two stations (if a a path is found).
        /// </summary>
        /// <param name="startStation">The start station.</param>
        /// <param name="endStation">The end station.</param>
        /// <returns></returns>
        /// <exception cref="System.Exception">There was no batteries available in the requested
        /// route.</exception>
        public IEnumerable<PartRoute> MinDistancePath(Station startStation, Station endStation)
        {
            var route = new Stack<PartRoute>();
            //Find the start node using a lambda expression on _nodes
            Node start = _nodes.Single(n => n.Station.Name == startStation.Name);
            //Find the end node using a lambda expression on _nodes
            Node end = _nodes.Single(n => n.Station.Name == endStation.Name);

            //Here the method FindMinDistancePath is called
            //This method does the work of creating a path
            //and returns a bool true if the path is found
            bool isConnected = FindMinDistancePath(start, end);

            //If a route could not be found an error is returned
            if (!isConnected)
            {
                throw new Exception("There was no batteries available in the requested route.");
            }

            //If a route is found the following loop creates the partroutes
            Node currentNode = end;
            while (currentNode != start)
            {
                currentNode.Visited = true;
                currentNode.EdgeCameFrom.Visited = true;

                // create part route
                var partRoute = new PartRoute
                {
                    LocationEnd = currentNode.Station,
                    LocationStart =
                        currentNode.EdgeCameFrom.FirstNode.Station == currentNode.Station
                            ? currentNode.EdgeCameFrom.SecondNode.Station
                            : currentNode.EdgeCameFrom.FirstNode.Station,
                    Distance = currentNode.EdgeCameFrom.Distance,
                    Time = currentNode.EdgeCameFrom.Time
                };
                //the new partroute is added to the top of the stack
                route.Push(partRoute);
                //The currentnode is set to the other node at the current 'edgecamefrom'
                currentNode = GetNeighbour(currentNode, currentNode.EdgeCameFrom);
            }
            //Marks the end node finished and returns the completed route
            end.Visited = true;

            return route;
        }

        /// <summary>
        /// This is the algorithm implementation, that finds the minimum distance path.
        ///
        /// (Dijkstra's algorithm)
        /// </summary>
        /// <param name="start">The start.</param>
        /// <param name="end">The end.</param>
        /// <returns>boolean telling if a route is found</returns>
        private bool FindMinDistancePath(Node start, Node end)
        {
            Boolean isConnected = true;
            _visitedNodes.Clear();
            _reachableNodes.Clear();
            Node currentNode = start;
            currentNode.Visited = true;
            start.TotalCost = 0;
            _visitedNodes.Add(currentNode);
            //This loop runs through the reachable nodes from a current node (this node changes during the algorithm)
            while (currentNode != end)
            {
                AddReachableNodes(currentNode);
                //Updates total costs for reachable nodes if lower through current node
                UpdateReachableNodesTotalCost(currentNode);

                //The graph is not connected if no reachable nodes are found
                if (_reachableNodes.ReachableNodes.Count == 0)
                {
                    isConnected = false;
                    break;
                }

                //Find the nearest reachable node
                var currentReachableNode = _reachableNodes.ReachableNodes[0];

                //Remove the node from the list of reachable node,
                //set the node to the current node and mark the node as visited
                _reachableNodes.RemoveReachableNode(currentReachableNode);
                currentNode.Visited = true;
                currentNode = currentReachableNode.Node;

                //remember the edge to the other node from which it came from
                //and mark this edge as visited
                currentNode.EdgeCameFrom = currentReachableNode.Edge;
                currentReachableNode.Edge.Visited = true;

                //add the node to the list of visited nodes
                _visitedNodes.Add(currentNode);
            }
            //Return the boolean telling if the graph was connected
            return isConnected;
        }

        /// <summary>
        /// This method adds the reachable nodes .
        /// </summary>
        /// <param name="node">The node.</param>
        private void AddReachableNodes(Node node)
        {
            foreach (var edge in node.Edges)
            {
                //Get the node in the other end of the edge
                var neighborNode = GetNeighbour(node, edge);

                //Gets the node it came from if any
                Node cameFromNode = node.EdgeCameFrom != null ? GetNeighbour(node, node.EdgeCameFrom) : null;

                //Make sure that it is not the previusly visited node that i came from
                if ((cameFromNode == null || neighborNode != cameFromNode) &&
                    //And make sure that the node is not already in the list of visited nodes
                    !_visitedNodes.Contains(neighborNode))
                {
                    ReachableNode rn;
                    //If there's already found a possible path to the neigbour node
                    if (_reachableNodes.HasNode(neighborNode))
                    {
                        //If the total cost through this node plus the distance to the neighbour node
                        //Is less than the previously found totalcost to the neighbour node
                        if (node.TotalCost + edge.Distance < neighborNode.TotalCost)
                        {
                            //Update the node's edge to this one replacing the previously found edge
                            rn = _reachableNodes.GetReachableNodeFromNode(neighborNode);
                            rn.Edge = edge;
                        }
                    }
                    //If a path has not been found before, make it a reachable node now
                    else
                    {
                        rn = new ReachableNode(neighborNode, edge);
                        _reachableNodes.AddReachableNode(rn);
                    }
                }
            }
        }

        /// <summary>
        /// Updates the reachable nodes total cost if lower. Also sorts the list of reachable nodes
        /// with smallest cost first
        /// </summary>
        /// <param name="node">The node.</param>
        private void UpdateReachableNodesTotalCost(Node node)
        {
            var currentCost = node.TotalCost;
            foreach (var rn in _reachableNodes.ReachableNodes)
            {
                //If totalcost equals -1 the node is unvisited
                //This updates the totalcost of a node if the current cost is lower
                if (currentCost + rn.Edge.Distance < rn.Node.TotalCost || rn.Node.TotalCost.Equals(-1))
                {
                    rn.Node.TotalCost = currentCost + rn.Edge.Distance;
                }
            }
            //Sort the reachable nodes in an order where smallest cost is put first
            _reachableNodes.SortReachableNodes();
        }

        private static Node GetNeighbour(Node node, Edge edge)
        {
            return edge.FirstNode == node ? edge.SecondNode : edge.FirstNode;
        }
    }
}